An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in Datacenters

摘要

In data-parallel computing frameworks, intermediate parallel data is oftenproduced at various stages which needs to be transferred among servers in thedatacenter network (e.g. the shuffle phase in MapReduce). A stage often cannotstart or be completed unless all the required data pieces from the precedingstage are received. \emph{Coflow} is a recently proposed networking abstractionto capture such communication patterns. We consider the problem of efficientlyscheduling coflows with release dates in a shared datacenter network so as tominimize the total weighted completion time of coflows. Several heuristics have been proposed recently to address this problem, aswell as a few polynomial-time approximation algorithms with provableperformance guarantees. Our main result in this paper is a polynomial-timedeterministic algorithm that improves the prior known results. Specifically, wepropose a deterministic algorithm with approximation ratio of $5$, whichimproves the prior best known ratio of $12$. For the special case when allcoflows are released at time zero, our deterministic algorithm obtainsapproximation ratio of $4$ which improves the prior best known ratio of $8$.The key ingredient of our approach is an improved linear program formulationfor sorting the coflows followed by a simple list scheduling policy. Extensivesimulation results, using both synthetic and real traffic traces, are presentedthat verify the performance of our algorithm and show improvement over theprior approaches.